class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size(),left=-1,right=n-1,cur=0;
        while(cur<n&&cur<=right)
        {
            if(nums[cur]==0) swap(nums[++left],nums[cur++]);
            else if(nums[cur]==1) cur++;
            else swap(nums[cur],nums[right--]);
        }
    }
};
